import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created whit IntelliJ IDEA.
 * Description：
 * User：ZHONGCHEN
 * Date:2022-02-19
 * Time:14:44
 */
/**
 * 969. 煎饼排序
 * 给你一个整数数组 arr ，请使用 煎饼翻转 完成对数组的排序。
 *
 * 一次煎饼翻转的执行过程如下：
 *
 * 选择一个整数 k ，1 <= k <= arr.length
 * 反转子数组 arr[0...k-1]（下标从 0 开始）
 * 例如，arr = [3,2,1,4] ，选择 k = 3 进行一次煎饼翻转，反转子数组 [3,2,1] ，得到 arr = [1,2,3,4] 。
 * 以数组形式返回能使 arr 有序的煎饼翻转操作所对应的 k 值序列。
 * 任何将数组排序且翻转次数在 10 * arr.length 范围内的有效答案都将被判断为正确。
 *
 * 示例 1：
 * 输入：[3,2,4,1]
 * 输出：[4,2,4,3]
 * 解释：
 * 我们执行 4 次煎饼翻转，k 值分别为 4，2，4，和 3。
 * 初始状态 arr = [3, 2, 4, 1]
 * 第一次翻转后（k = 4）：arr = [1, 4, 2, 3]
 * 第二次翻转后（k = 2）：arr = [4, 1, 2, 3]
 * 第三次翻转后（k = 4）：arr = [3, 2, 1, 4]
 * 第四次翻转后（k = 3）：arr = [1, 2, 3, 4]，此时已完成排序。
 * */
/**
 * 3 2 4 1
 * 最大值在第三位：前三位翻转
 * 4 2 3 1
 * 全部翻转：
 * 1 3 2 4
 * (此时4归位)
 * 在看次大值：在第二位，前二位翻转：
 * 3 1 2 4：
 * 前三位翻转：
 * 2 1 3 4
 * (此时3归位)
 * 第三大值本来在第一个，前两位翻转：1 2 3 4
 */
public class TestDemo {
    public static boolean sort(int[] arr) {
        for (int i = 0; i < arr.length-1; i++) {
            if (arr[i] > arr[i + 1]) {
                return false;
            }
        }
        return true;
    }

    public static int findMaxIdea(int[] arr, int arrlength) {
        int maxIdea = 0;
        int max = 0;
        for (int i = 0; i < arrlength; i++) {
            if (arr[i] > max) {
                max = arr[i];
                maxIdea = i;
            }
        }
        return maxIdea;
    }

    public static void reverse(int[] arr, int start, int end) {
        while (start < end) {
            int tmp = arr[start];
            arr[start] = arr[end];
            arr[end] = tmp;
            start++;
            end--;
        }
    }

    public static List<Integer> pancakeSort(int[] arr) {
        //list用于存储答案
        List<Integer> list = new ArrayList<>();
        int arrlength = arr.length;
        //判断数组是否有序
        while (!sort(arr)) {
            //找到该需要排序的数组中的最大值的下标
            int maxidea = findMaxIdea(arr, arrlength);
            //如果数组的最大值刚刚好等于arrlength
            // 则说明该数字位于正确的位置 无需反转数组并且将需要排序的数组长度减1
            if (maxidea == arrlength - 1) {
                arrlength--;
                continue;
            } else {
                //如果数组的最大值 刚刚好位于第一位,则将需要排序的数组都进行反转 并且记录答案
                if (maxidea == 0) {
                    reverse(arr, 0, arrlength-1);
                    list.add(arrlength);
                    arrlength--;
                }else {
                    //如果不在第一位 则需要经过反转将最大的数字反转到数组的第一位并且记录答案
                    reverse(arr,0,maxidea);
                    list.add(maxidea+1);
                }
            }
        }
        return list;
    }

    public static void main(String[] args) {
        int[] arr = {1,2,3,4};
        System.out.println(pancakeSort(arr));
    }
}
